#include <stdio.h>
#include <stdlib.h>

/* 邻接矩阵表示的图定义 */
typedef enum { false, true } bool;
typedef int Vertex; /* 顶点编号类型 */
typedef int GElemSet; /* 边权重类型 */
typedef bool VertInfo; /* 顶点信息类型 */
typedef struct MGraphNode *MGraph; /* 邻接矩阵表示的图 */
struct MGraphNode {
    int n_verts; /* 顶点数 */
    int m_edges; /* 边数 */
    GElemSet **edge_matrix;/* 邻接矩阵 */
    VertInfo *visited; /* 存储顶点访问标识 */
    GElemSet no_edge_value; /* 表述没有边时的权重值 */
    bool directed; /* true为有向图，false为无向图 */
};

void InitGraph(MGraph graph, int kMaxVertex, GElemSet no_edge_value,
               bool directed);
bool ExistEdge(MGraph graph, Vertex u, Vertex v);
void InsertEdge(MGraph graph, Vertex u, Vertex v, GElemSet weight);
/* 邻接矩阵表示的图定义 结束 */

#define kMaxN 1000
MGraph BuildGraph() {
    /* 读入输入，建立图 */
    MGraph graph;
    int n, m, i;
    Vertex u, v;

    graph = (MGraph)malloc(sizeof(struct MGraphNode));
    InitGraph(graph, kMaxN, 0, false);
    scanf("%d %d\n", &n, &m);
    graph->n_verts = n;
    for (v = 0; v < n; v++) {
        graph->visited[v] = false;
    }
    for (i = 0; i < m; i++) {
        scanf("%d %d\n", &u, &v);
        /* 注意顶点编号与数组下标差1 */
        InsertEdge(graph, u - 1, v - 1, 1);
    }
    return graph;
}

void DFSv(MGraph graph, Vertex v) {
    /* 深度优先搜索 */
    Vertex u;

    graph->visited[v] = true; /* 将访问到的顶点进行标记 */
    for (u = 0; u < graph->n_verts; u++) {
        if (graph->edge_matrix[v][u] != graph->no_edge_value
        && graph->visited[u] == false)
            /* 若u和v之间有边 */
            DFSv(graph, u);
    }
}

bool IsConnected(MGraph graph) {
    /* 检查图是否连通 */
    Vertex v;

    DFSv(graph, 0);
    for (v = 0; v < graph->n_verts; v++) {
        if (graph->visited[v] == false)
            break; /* 发现DFS没访问到的顶点 */
    }
    /* 若v==graph->n_verts说明所有顶点都被访问到 */
    return (v == graph->n_verts);
}

bool CheckDegrees(MGraph graph) {
    /* 检查顶点的度是否全为偶数 */
    int degree;
    Vertex u, v;

    for (u = 0; u < graph->n_verts; u++) {
        degree = 0;
        for (v = 0; v < graph->n_verts; v++) {
            degree += graph->edge_matrix[u][v];
        }
        if (degree % 2 == 1) {
            /* 发现奇数度的顶点则返回false */
            return false;
        }
    }
    return true; /* 全是偶数度的顶点则返回true */
}

int main(void) {
    MGraph graph;
    Vertex u, v;

    graph = BuildGraph();
    if (IsConnected(graph) == true) {
        if (CheckDegrees(graph) == true) {
            printf("1\n"); /* 全是偶数度的顶点 */
        } else { /* 发现奇数度的顶点 */
            printf("0\n");
        }
    } else { /* 图不连通，答案是0 */
        printf("0\n");
    }

    return 0;
}

void InitGraph(MGraph graph, int kMaxVertex, GElemSet no_edge_value,
               bool directed) {
    /* 初始化一个空的图 */
    GElemSet *array;
    int i;
    Vertex u, v;

    graph->n_verts = 0;
    graph->m_edges = 0;
    /* 声明二维数组graph->edge_matrix[kMaxVertex][kMaxVertex] */
    array = (GElemSet *)malloc(sizeof(GElemSet) * kMaxVertex * kMaxVertex);
    graph->edge_matrix = (GElemSet **)malloc(sizeof(GElemSet *) * kMaxVertex);
    for (i = 0; i < kMaxVertex; i++) {
        graph->edge_matrix[i] = &array[i * kMaxVertex];
    }
    /* 声明顶点信息数组graph->ver_list[kMaxVertex] */
    graph->visited = (VertInfo *)malloc(sizeof(VertInfo) * kMaxVertex);
    graph->no_edge_value = no_edge_value;
    graph->directed = directed;
    for (u = 0; u < kMaxVertex; u++) {
        for (v = 0; v < kMaxVertex; v++) {
            graph->edge_matrix[u][v] = graph->no_edge_value;
        }
    }
}

bool ExistEdge(MGraph graph, Vertex u, Vertex v) {
    bool ret = false;

    if (u < graph->n_verts && v < graph->n_verts) {
        if (u != v && graph->edge_matrix[u][v] != graph->no_edge_value) {
            ret = true;
        }
    }
    return ret;
}

void InsertEdge(MGraph graph, Vertex u, Vertex v, GElemSet weight) {
    if (ExistEdge(graph, u, v) == false) {
        graph->edge_matrix[u][v] = weight;
        graph->m_edges++;
        if (graph->directed == false) {
            graph->edge_matrix[v][u] = weight;
        }
    }
}